package com.justnow.offer;

import java.util.HashMap;

/**
 * 前序遍历 preorder = [3,9,20,15,7]
 * 中序遍历 inorder = [9,3,15,20,7]
 */
public class Solution07 {
    HashMap<Integer, Integer> map = new HashMap<>();//标记中序遍历
    int[] tmp;//保留的先序遍历
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.tmp = preorder;
        for (int i = 0; i < tmp.length; i++) {
            map.put(inorder[i], i);
        }
        return recursive(0, 0, inorder.length - 1);
    }


    /**
     *
     * @param pre_root_idx 先序遍历的索引，表示根节点在先序遍历中的索引
     * @param in_left_idx  中序遍历的索引，表示根节点及其子节点在中序遍历中的左边界
     * @param in_right_idx 中序遍历的索引，表示根节点及其子节点在中序遍历中的右边界
     * @return
     */
    public TreeNode recursive(int pre_root_idx, int in_left_idx, int in_right_idx) {
        //如果左边界大于右边界，递归结束了
        if (in_left_idx > in_right_idx) return null;

        //根据pre_root_idx，直接得出根节点的val值，然后创建根节点。
        TreeNode root = new TreeNode(tmp[pre_root_idx]);

        //根据直接生成好的map，使用root.val查找到该根节点在中序遍历中的索引。
        int idx = map.get(root.val);

        //由idx将中序遍历分为两部分，即根节点的左子节点为根节点为一部分和根节点的右子节点为根节点为一部分，先看左子节点


        //此时，以左字节为根节点的话，那么，
        //首先根节点在先序遍历中的索引为pre_root_idx + 1
        //然后，本次递归中的左边界为：in_left_idx
        //本次递归中的右边界为：idx - 1
        root.left = recursive(pre_root_idx+1, in_left_idx, idx-1);

        //接下来，以右子节点为根节点
        //首先，根节点在先序遍历中的索引为：pre_root_idx + 左子节点及其子节点的长度，即（pre_root_idx + idx - in_left_idx + 1）
        //然后，本次递归的左边界是：idx + 1
        //本次递归中的右边界为：in_right_idx
        root.right = recursive(pre_root_idx + (idx - 1 - in_left_idx + 1) + 1, idx + 1, in_right_idx);

        //至此，一次递归中树种的根节点，及其左右子节点的创建就搞定了，最后再返回root节点即可
        return root;
    }

    public static void main(String[] args) {
        Solution07 solution07 = new Solution07();
        int[] pre = {3,9,20,15,7};
        int[] in = {9,3,15,20,7};
        TreeNode node = solution07.buildTree(pre, in);


    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode (int val) {
        this.val = val;
    }
}
